What is Binary Search

Binary search is a search method that works only on sorted datasets or arrays.It uses the divide and conquer strategy.
The process starts by examining the middle element of the dataset and splits the dataset into two subparts.It then determine which half to keep for further searching by comparing the desired value with the middle element.
If the middle element is less than the target value, it keeps the right half; otherwise. it keeps the left half.This process repeats until the target value is found or there are no elements left in the search section.

binary search 是一種搜尋方法，用於已排序好的 dataset/array，該方法使用了 divide and conquer(分而治之) 的概念

從 input dataset 中間的 index 開始，將 dataset 分割為左右兩個子部分
若目標值小於中間元素，則取左半部繼續分割
若目標值大於中間元素，則取右半部繼續分割
直到找到與目標相符的值或該子部分中沒有任何元素存在，便結束搜尋

Limitation of Binary Search

requires a sorted array 僅適用於 **已經排序好的 dataset/array **

Steps of Binary Search

圖片來源

1. Start 取得 dataset 中間的索引值
   Find the middle index of the dataset
2. Compare 比較
   Check id the middle element matches the desired element
3. Choose which half to take 選擇左半部或右半部，以進行下一輪比較
   If the desired element is larger than the middle element, pick the right half of the dataset; otherwise, pick the left half.
4. Move middle index 移動索引值
   Repeat step 1-3 with the selected half until no elements are left.
5. Result 回傳搜尋結果
   If the element equal to the desired value, return the index of that element else return false or -1.

Complexity of Binary Search

• Best Case: O(1)
  在 dataset 中間就找到目標值
• Average Case: O(log n)
• Worst Case: O(log n)
  遍歷整個資料集都沒找到目標

Implementation of Binary Search

• 為什麼用while loop?
  因為不知道確切數字會執行幾次
• 藉由 min~max 定義不斷分割的子部分範圍

let dataSet = [0, 1, 2, 3, 4, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 23, 24, 26, 27, 28, 29, 30, 31, 32, 33, 34, 36, 37, 38, 40, 42, 45, 47, 48, 49, 51, 53, 55, 59, 61, 62, 63, 64, 65, 66, 68, 69, 70, 72, 73, 74, 75, 76, 77, 79, 80, 81, 83, 85, 86, 86, 87, 88, 89, 91, 92, 93, 95, 95, 97, 99, 103, 108, 112, 155, 179, 213];

function binarySearch(arraySet, n) {
    let min = 0,
        max = arraySet.length - 1;
    let middle;

    while (min <= max) {
        middle = min + Math.floor((max - min) / 2);
        console.log(`min:${min} max:${max} middle:${middle}`);
        if (arraySet[middle] == n) {
            console.log(`find ${n}  with index ${middle}`);
            return middle;
        }

        if (arraySet[middle] > n) {
            // pick left sub-part, move index of min to middle+1
            max = middle - 1;
        } else {
            min = middle + 1;
        }
    }
    console.log(`can not find ${n}`);
    return -1;
}

binarySearch(newData, 30); // 25
binarySearch( dataSet, 0); // 0
binarySearch( dataSet, 265); // -1

相關資源

DSA Binary Search
https://www.w3schools.com/dsa/dsa_algo_binarysearch.php
Binary Search
https://www.geeksforgeeks.org/binary-search/
Binary Search Algorithm
https://www.tutorialspoint.com/data_structures_algorithms/binary_search_algorithm.htm

https://medium.com/appworks-school/binary-search-%E9%82%A3%E4%BA%9B%E8%97%8F%E5%9C%A8%E7%B4%B0%E7%AF%80%E8%A3%A1%E7%9A%84%E9%AD%94%E9%AC%BC-%E4%B8%80-%E5%9F%BA%E7%A4%8E%E4%BB%8B%E7%B4%B9-dd2cd804aee1